home *** CD-ROM | disk | FTP | other *** search
/ Scene Storm / Scene Storm - Volume 1.iso / coding / c / jpeglib5b / jdhuff.c < prev    next >
C/C++ Source or Header  |  1980-01-12  |  22KB  |  689 lines
  1. /*
  2.  * jdhuff.c
  3.  *
  4.  * Copyright (C) 1991-1994, Thomas G. Lane.
  5.  * This file is part of the Independent JPEG Group's software.
  6.  * For conditions of distribution and use, see the accompanying README file.
  7.  *
  8.  * This file contains Huffman entropy decoding routines.
  9.  *
  10.  * Much of the complexity here has to do with supporting input suspension.
  11.  * If the data source module demands suspension, we want to be able to back
  12.  * up to the start of the current MCU.  To do this, we copy state variables
  13.  * into local working storage, and update them back to the permanent JPEG
  14.  * objects only upon successful completion of an MCU.
  15.  */
  16.  
  17. #define JPEG_INTERNALS
  18. #include "jinclude.h"
  19. #include "jpeglib.h"
  20.  
  21.  
  22. /* Derived data constructed for each Huffman table */
  23.  
  24. #define HUFF_LOOKAHEAD    8    /* # of bits of lookahead */
  25.  
  26. typedef struct {
  27.   /* Basic tables: (element [0] of each array is unused) */
  28.   INT32 mincode[17];        /* smallest code of length k */
  29.   INT32 maxcode[18];        /* largest code of length k (-1 if none) */
  30.   /* (maxcode[17] is a sentinel to ensure huff_DECODE terminates) */
  31.   int valptr[17];        /* huffval[] index of 1st symbol of length k */
  32.  
  33.   /* Back link to public Huffman table (needed only in slow_DECODE) */
  34.   JHUFF_TBL *pub;
  35.  
  36.   /* Lookahead tables: indexed by the next HUFF_LOOKAHEAD bits of
  37.    * the input data stream.  If the next Huffman code is no more
  38.    * than HUFF_LOOKAHEAD bits long, we can obtain its length and
  39.    * the corresponding symbol directly from these tables.
  40.    */
  41.   int look_nbits[1<<HUFF_LOOKAHEAD]; /* # bits, or 0 if too long */
  42.   UINT8 look_sym[1<<HUFF_LOOKAHEAD]; /* symbol, or unused */
  43. } D_DERIVED_TBL;
  44.  
  45. /* Expanded entropy decoder object for Huffman decoding.
  46.  *
  47.  * The savable_state subrecord contains fields that change within an MCU,
  48.  * but must not be updated permanently until we complete the MCU.
  49.  */
  50.  
  51. typedef struct {
  52.   INT32 get_buffer;        /* current bit-extraction buffer */
  53.   int bits_left;        /* # of unused bits in it */
  54.   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
  55. } savable_state;
  56.  
  57. /* This macro is to work around compilers with missing or broken
  58.  * structure assignment.  You'll need to fix this code if you have
  59.  * such a compiler and you change MAX_COMPS_IN_SCAN.
  60.  */
  61.  
  62. #ifndef NO_STRUCT_ASSIGN
  63. #define ASSIGN_STATE(dest,src)  ((dest) = (src))
  64. #else
  65. #if MAX_COMPS_IN_SCAN == 4
  66. #define ASSIGN_STATE(dest,src)  \
  67.     ((dest).get_buffer = (src).get_buffer, \
  68.      (dest).bits_left = (src).bits_left, \
  69.      (dest).last_dc_val[0] = (src).last_dc_val[0], \
  70.      (dest).last_dc_val[1] = (src).last_dc_val[1], \
  71.      (dest).last_dc_val[2] = (src).last_dc_val[2], \
  72.      (dest).last_dc_val[3] = (src).last_dc_val[3])
  73. #endif
  74. #endif
  75.  
  76.  
  77. typedef struct {
  78.   struct jpeg_entropy_decoder pub; /* public fields */
  79.  
  80.   savable_state saved;        /* Bit buffer & DC state at start of MCU */
  81.  
  82.   /* These fields are NOT loaded into local working state. */
  83.   unsigned int restarts_to_go;    /* MCUs left in this restart interval */
  84.   boolean printed_eod;        /* flag to suppress extra end-of-data msgs */
  85.  
  86.   /* Pointers to derived tables (these workspaces have image lifespan) */
  87.   D_DERIVED_TBL * dc_derived_tbls[NUM_HUFF_TBLS];
  88.   D_DERIVED_TBL * ac_derived_tbls[NUM_HUFF_TBLS];
  89. } huff_entropy_decoder;
  90.  
  91. typedef huff_entropy_decoder * huff_entropy_ptr;
  92.  
  93. /* Working state while scanning an MCU.
  94.  * This struct contains all the fields that are needed by subroutines.
  95.  */
  96.  
  97. typedef struct {
  98.   int unread_marker;        /* nonzero if we have hit a marker */
  99.   const JOCTET * next_input_byte; /* => next byte to read from source */
  100.   size_t bytes_in_buffer;    /* # of bytes remaining in source buffer */
  101.   savable_state cur;        /* Current bit buffer & DC state */
  102.   j_decompress_ptr cinfo;    /* fill_bit_buffer needs access to this */
  103. } working_state;
  104.  
  105.  
  106. /* Forward declarations */
  107. LOCAL void fix_huff_tbl JPP((j_decompress_ptr cinfo, JHUFF_TBL * htbl,
  108.                  D_DERIVED_TBL ** pdtbl));
  109.  
  110.  
  111. /*
  112.  * Initialize for a Huffman-compressed scan.
  113.  */
  114.  
  115. METHODDEF void
  116. start_pass_huff_decoder (j_decompress_ptr cinfo)
  117. {
  118.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  119.   int ci, dctbl, actbl;
  120.   jpeg_component_info * compptr;
  121.  
  122.   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
  123.     compptr = cinfo->cur_comp_info[ci];
  124.     dctbl = compptr->dc_tbl_no;
  125.     actbl = compptr->ac_tbl_no;
  126.     /* Make sure requested tables are present */
  127.     if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS ||
  128.     cinfo->dc_huff_tbl_ptrs[dctbl] == NULL)
  129.       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
  130.     if (actbl < 0 || actbl >= NUM_HUFF_TBLS ||
  131.     cinfo->ac_huff_tbl_ptrs[actbl] == NULL)
  132.       ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
  133.     /* Compute derived values for Huffman tables */
  134.     /* We may do this more than once for a table, but it's not expensive */
  135.     fix_huff_tbl(cinfo, cinfo->dc_huff_tbl_ptrs[dctbl],
  136.          & entropy->dc_derived_tbls[dctbl]);
  137.     fix_huff_tbl(cinfo, cinfo->ac_huff_tbl_ptrs[actbl],
  138.          & entropy->ac_derived_tbls[actbl]);
  139.     /* Initialize DC predictions to 0 */
  140.     entropy->saved.last_dc_val[ci] = 0;
  141.   }
  142.  
  143.   /* Initialize private state variables */
  144.   entropy->saved.bits_left = 0;
  145.   entropy->saved.get_buffer = 0; /* unnecessary, but keeps Purify quiet */
  146.   entropy->printed_eod = FALSE;
  147.  
  148.   /* Initialize restart counter */
  149.   entropy->restarts_to_go = cinfo->restart_interval;
  150. }
  151.  
  152.  
  153. LOCAL void
  154. fix_huff_tbl (j_decompress_ptr cinfo, JHUFF_TBL * htbl, D_DERIVED_TBL ** pdtbl)
  155. /* Compute the derived values for a Huffman table */
  156. {
  157.   D_DERIVED_TBL *dtbl;
  158.   int p, i, l, si;
  159.   int lookbits, ctr;
  160.   char huffsize[257];
  161.   unsigned int huffcode[257];
  162.   unsigned int code;
  163.  
  164.   /* Allocate a workspace if we haven't already done so. */
  165.   if (*pdtbl == NULL)
  166.     *pdtbl = (D_DERIVED_TBL *)
  167.       (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  168.                   SIZEOF(D_DERIVED_TBL));
  169.   dtbl = *pdtbl;
  170.   dtbl->pub = htbl;        /* fill in back link */
  171.   
  172.   /* Figure C.1: make table of Huffman code length for each symbol */
  173.   /* Note that this is in code-length order. */
  174.  
  175.   p = 0;
  176.   for (l = 1; l <= 16; l++) {
  177.     for (i = 1; i <= (int) htbl->bits[l]; i++)
  178.       huffsize[p++] = (char) l;
  179.   }
  180.   huffsize[p] = 0;
  181.   
  182.   /* Figure C.2: generate the codes themselves */
  183.   /* Note that this is in code-length order. */
  184.   
  185.   code = 0;
  186.   si = huffsize[0];
  187.   p = 0;
  188.   while (huffsize[p]) {
  189.     while (((int) huffsize[p]) == si) {
  190.       huffcode[p++] = code;
  191.       code++;
  192.     }
  193.     code <<= 1;
  194.     si++;
  195.   }
  196.  
  197.   /* Figure F.15: generate decoding tables for bit-sequential decoding */
  198.  
  199.   p = 0;
  200.   for (l = 1; l <= 16; l++) {
  201.     if (htbl->bits[l]) {
  202.       dtbl->valptr[l] = p; /* huffval[] index of 1st symbol of code length l */
  203.       dtbl->mincode[l] = huffcode[p]; /* minimum code of length l */
  204.       p += htbl->bits[l];
  205.       dtbl->maxcode[l] = huffcode[p-1]; /* maximum code of length l */
  206.     } else {
  207.       dtbl->maxcode[l] = -1;    /* -1 if no codes of this length */
  208.     }
  209.   }
  210.   dtbl->maxcode[17] = 0xFFFFFL; /* ensures huff_DECODE terminates */
  211.  
  212.   /* Compute lookahead tables to speed up decoding.
  213.    * First we set all the table entries to 0, indicating "too long";
  214.    * then we iterate through the Huffman codes that are short enough and
  215.    * fill in all the entries that correspond to bit sequences starting
  216.    * with that code.
  217.    */
  218.  
  219.   MEMZERO(dtbl->look_nbits, SIZEOF(dtbl->look_nbits));
  220.  
  221.   p = 0;
  222.   for (l = 1; l <= HUFF_LOOKAHEAD; l++) {
  223.     for (i = 1; i <= (int) htbl->bits[l]; i++, p++) {
  224.       /* l = current code's length, p = its index in huffcode[] & huffval[]. */
  225.       /* Generate left-justified code followed by all possible bit sequences */
  226.       lookbits = huffcode[p] << (HUFF_LOOKAHEAD-l);
  227.       for (ctr = 1 << (HUFF_LOOKAHEAD-l); ctr > 0; ctr--) {
  228.     dtbl->look_nbits[lookbits] = l;
  229.     dtbl->look_sym[lookbits] = htbl->huffval[p];
  230.     lookbits++;
  231.       }
  232.     }
  233.   }
  234. }
  235.  
  236.  
  237. /*
  238.  * Code for extracting the next N bits from the input stream.
  239.  * (N never exceeds 15 for JPEG data.)
  240.  * This needs to go as fast as possible!
  241.  *
  242.  * We read source bytes into get_buffer and dole out bits as needed.
  243.  * If get_buffer already contains enough bits, they are fetched in-line
  244.  * by the macros check_bit_buffer and get_bits.  When there aren't enough
  245.  * bits, fill_bit_buffer is called; it will attempt to fill get_buffer to
  246.  * the "high water mark" (not just to the number of bits needed; this reduces
  247.  * the function-call overhead cost of entering fill_bit_buffer).
  248.  * Note that fill_bit_buffer may return FALSE to indicate suspension.
  249.  * On TRUE return, fill_bit_buffer guarantees that get_buffer contains
  250.  * at least the requested number of bits --- dummy zeroes are inserted if
  251.  * necessary.
  252.  *
  253.  * On most machines MIN_GET_BITS should be 25 to allow the full 32-bit width
  254.  * of get_buffer to be used.  (On machines with wider words, an even larger
  255.  * buffer could be used.)  However, on some machines 32-bit shifts are
  256.  * quite slow and take time proportional to the number of places shifted.
  257.  * (This is true with most PC compilers, for instance.)  In this case it may
  258.  * be a win to set MIN_GET_BITS to the minimum value of 15.  This reduces the
  259.  * average shift distance at the cost of more calls to fill_bit_buffer.
  260.  */
  261.  
  262. #ifdef SLOW_SHIFT_32
  263. #define MIN_GET_BITS  15    /* minimum allowable value */
  264. #else
  265. #define MIN_GET_BITS  25    /* max value for 32-bit get_buffer */
  266. #endif
  267.  
  268.  
  269. LOCAL boolean
  270. fill_bit_buffer (working_state * state, int nbits)
  271. /* Load up the bit buffer to a depth of at least nbits */
  272. {
  273.   /* Copy heavily used state fields into locals (hopefully registers) */
  274.   register const JOCTET * next_input_byte = state->next_input_byte;
  275.   register size_t bytes_in_buffer = state->bytes_in_buffer;
  276.   register INT32 get_buffer = state->cur.get_buffer;
  277.   register int bits_left = state->cur.bits_left;
  278.   register int c;
  279.  
  280.   /* Attempt to load at least MIN_GET_BITS bits into get_buffer. */
  281.   /* (It is assumed that no request will be for more than that many bits.) */
  282.  
  283.   while (bits_left < MIN_GET_BITS) {
  284.     /* Attempt to read a byte */
  285.     if (state->unread_marker != 0)
  286.       goto no_more_data;    /* can't advance past a marker */
  287.  
  288.     if (bytes_in_buffer == 0) {
  289.       if (! (*state->cinfo->src->fill_input_buffer) (state->cinfo))
  290.     return FALSE;
  291.       next_input_byte = state->cinfo->src->next_input_byte;
  292.       bytes_in_buffer = state->cinfo->src->bytes_in_buffer;
  293.     }
  294.     bytes_in_buffer--;
  295.     c = GETJOCTET(*next_input_byte++);
  296.  
  297.     /* If it's 0xFF, check and discard stuffed zero byte */
  298.     if (c == 0xFF) {
  299.       do {
  300.     if (bytes_in_buffer == 0) {
  301.       if (! (*state->cinfo->src->fill_input_buffer) (state->cinfo))
  302.         return FALSE;
  303.       next_input_byte = state->cinfo->src->next_input_byte;
  304.       bytes_in_buffer = state->cinfo->src->bytes_in_buffer;
  305.     }
  306.     bytes_in_buffer--;
  307.     c = GETJOCTET(*next_input_byte++);
  308.       } while (c == 0xFF);
  309.  
  310.       if (c == 0) {
  311.     /* Found FF/00, which represents an FF data byte */
  312.     c = 0xFF;
  313.       } else {
  314.     /* Oops, it's actually a marker indicating end of compressed data. */
  315.     /* Better put it back for use later */
  316.     state->unread_marker = c;
  317.  
  318.       no_more_data:
  319.     /* There should be enough bits still left in the data segment; */
  320.     /* if so, just break out of the outer while loop. */
  321.     if (bits_left >= nbits)
  322.       break;
  323.     /* Uh-oh.  Report corrupted data to user and stuff zeroes into
  324.      * the data stream, so that we can produce some kind of image.
  325.      * Note that this will be repeated for each byte demanded for the
  326.      * rest of the segment; this is slow but not unreasonably so.
  327.      * The main thing is to avoid getting a zillion warnings, hence
  328.      * we use a flag to ensure that only one warning appears.
  329.      */
  330.     if (! ((huff_entropy_ptr) state->cinfo->entropy)->printed_eod) {
  331.       WARNMS(state->cinfo, JWRN_HIT_MARKER);
  332.       ((huff_entropy_ptr) state->cinfo->entropy)->printed_eod = TRUE;
  333.     }
  334.     c = 0;            /* insert a zero byte into bit buffer */
  335.       }
  336.     }
  337.  
  338.     /* OK, load c into get_buffer */
  339.     get_buffer = (get_buffer << 8) | c;
  340.     bits_left += 8;
  341.   }
  342.  
  343.   /* Unload the local registers */
  344.   state->next_input_byte = next_input_byte;
  345.   state->bytes_in_buffer = bytes_in_buffer;
  346.   state->cur.get_buffer = get_buffer;
  347.   state->cur.bits_left = bits_left;
  348.  
  349.   return TRUE;
  350. }
  351.  
  352.  
  353. /*
  354.  * These macros provide the in-line portion of bit fetching.
  355.  * Use check_bit_buffer to ensure there are N bits in get_buffer
  356.  * before using get_bits, peek_bits, or drop_bits.
  357.  *    check_bit_buffer(state,n,action);
  358.  *        Ensure there are N bits in get_buffer; if suspend, take action.
  359.  *      val = get_bits(state,n);
  360.  *        Fetch next N bits.
  361.  *      val = peek_bits(state,n);
  362.  *        Fetch next N bits without removing them from the buffer.
  363.  *    drop_bits(state,n);
  364.  *        Discard next N bits.
  365.  * The value N should be a simple variable, not an expression, because it
  366.  * is evaluated multiple times.
  367.  */
  368.  
  369. #define check_bit_buffer(state,nbits,action) \
  370.     { if ((state).cur.bits_left < (nbits))  \
  371.         if (! fill_bit_buffer(&(state), nbits))  \
  372.           { action; } }
  373.  
  374. #define get_bits(state,nbits) \
  375.     (((int) ((state).cur.get_buffer >> ((state).cur.bits_left -= (nbits)))) & ((1<<(nbits))-1))
  376.  
  377. #define peek_bits(state,nbits) \
  378.     (((int) ((state).cur.get_buffer >> ((state).cur.bits_left -  (nbits)))) & ((1<<(nbits))-1))
  379.  
  380. #define drop_bits(state,nbits) \
  381.     ((state).cur.bits_left -= (nbits))
  382.  
  383.  
  384. /*
  385.  * Code for extracting next Huffman-coded symbol from input bit stream.
  386.  * We use a lookahead table to process codes of up to HUFF_LOOKAHEAD bits
  387.  * without looping.  Usually, more than 95% of the Huffman codes will be 8
  388.  * or fewer bits long.  The few overlength codes are handled with a loop.
  389.  * The primary case is made a macro for speed reasons; the secondary
  390.  * routine slow_DECODE is rarely entered and need not be inline code.
  391.  *
  392.  * Notes about the huff_DECODE macro:
  393.  * 1. Near the end of the data segment, we may fail to get enough bits
  394.  *    for a lookahead.  In that case, we do it the hard way.
  395.  * 2. If the lookahead table contains no entry, the next code must be
  396.  *    more than HUFF_LOOKAHEAD bits long.
  397.  * 3. slow_DECODE returns -1 if forced to suspend.
  398.  */
  399.  
  400. #define huff_DECODE(result,state,htbl,donelabel) \
  401. { if (state.cur.bits_left < HUFF_LOOKAHEAD) {  \
  402.     if (! fill_bit_buffer(&state, 0)) return FALSE;  \
  403.     if (state.cur.bits_left < HUFF_LOOKAHEAD) {  \
  404.       if ((result = slow_DECODE(&state, htbl, 1)) < 0) return FALSE;  \
  405.       goto donelabel;  \
  406.     }  \
  407.   }  \
  408.   { register int nb, look;  \
  409.     look = peek_bits(state, HUFF_LOOKAHEAD);  \
  410.     if ((nb = htbl->look_nbits[look]) != 0) {  \
  411.       drop_bits(state, nb);  \
  412.       result = htbl->look_sym[look];  \
  413.     } else {  \
  414.       if ((result = slow_DECODE(&state, htbl, HUFF_LOOKAHEAD+1)) < 0)  \
  415.     return FALSE;  \
  416.     }  \
  417.   }  \
  418. donelabel:;  \
  419. }
  420.  
  421.   
  422. LOCAL int
  423. slow_DECODE (working_state * state, D_DERIVED_TBL * htbl, int min_bits)
  424. {
  425.   register int l = min_bits;
  426.   register INT32 code;
  427.  
  428.   /* huff_DECODE has determined that the code is at least min_bits */
  429.   /* bits long, so fetch that many bits in one swoop. */
  430.  
  431.   check_bit_buffer(*state, l, return -1);
  432.   code = get_bits(*state, l);
  433.  
  434.   /* Collect the rest of the Huffman code one bit at a time. */
  435.   /* This is per Figure F.16 in the JPEG spec. */
  436.  
  437.   while (code > htbl->maxcode[l]) {
  438.     code <<= 1;
  439.     check_bit_buffer(*state, 1, return -1);
  440.     code |= get_bits(*state, 1);
  441.     l++;
  442.   }
  443.  
  444.   /* With garbage input we may reach the sentinel value l = 17. */
  445.  
  446.   if (l > 16) {
  447.     WARNMS(state->cinfo, JWRN_HUFF_BAD_CODE);
  448.     return 0;            /* fake a zero as the safest result */
  449.   }
  450.  
  451.   return htbl->pub->huffval[ htbl->valptr[l] +
  452.                 ((int) (code - htbl->mincode[l])) ];
  453. }
  454.  
  455.  
  456. /* Figure F.12: extend sign bit.
  457.  * On some machines, a shift and add will be faster than a table lookup.
  458.  */
  459.  
  460. #ifdef AVOID_TABLES
  461.  
  462. #define huff_EXTEND(x,s)  ((x) < (1<<((s)-1)) ? (x) + (((-1)<<(s)) + 1) : (x))
  463.  
  464. #else
  465.  
  466. #define huff_EXTEND(x,s)  ((x) < extend_test[s] ? (x) + extend_offset[s] : (x))
  467.  
  468. static const int extend_test[16] =   /* entry n is 2**(n-1) */
  469.   { 0, 0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
  470.     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000 };
  471.  
  472. static const int extend_offset[16] = /* entry n is (-1 << n) + 1 */
  473.   { 0, ((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1, ((-1)<<4) + 1,
  474.     ((-1)<<5) + 1, ((-1)<<6) + 1, ((-1)<<7) + 1, ((-1)<<8) + 1,
  475.     ((-1)<<9) + 1, ((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
  476.     ((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1 };
  477.  
  478. #endif /* AVOID_TABLES */
  479.  
  480.  
  481. /*
  482.  * Check for a restart marker & resynchronize decoder.
  483.  * Returns FALSE if must suspend.
  484.  */
  485.  
  486. LOCAL boolean
  487. process_restart (j_decompress_ptr cinfo)
  488. {
  489.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  490.   int ci;
  491.  
  492.   /* Throw away any unused bits remaining in bit buffer; */
  493.   /* include any full bytes in next_marker's count of discarded bytes */
  494.   cinfo->marker->discarded_bytes += entropy->saved.bits_left / 8;
  495.   entropy->saved.bits_left = 0;
  496.  
  497.   /* Advance past the RSTn marker */
  498.   if (! (*cinfo->marker->read_restart_marker) (cinfo))
  499.     return FALSE;
  500.  
  501.   /* Re-initialize DC predictions to 0 */
  502.   for (ci = 0; ci < cinfo->comps_in_scan; ci++)
  503.     entropy->saved.last_dc_val[ci] = 0;
  504.  
  505.   /* Reset restart counter */
  506.   entropy->restarts_to_go = cinfo->restart_interval;
  507.  
  508.   entropy->printed_eod = FALSE; /* next segment can get another warning */
  509.  
  510.   return TRUE;
  511. }
  512.  
  513.  
  514. /* ZAG[i] is the natural-order position of the i'th element of zigzag order.
  515.  * If the incoming data is corrupted, decode_mcu could attempt to
  516.  * reference values beyond the end of the array.  To avoid a wild store,
  517.  * we put some extra zeroes after the real entries.
  518.  */
  519.  
  520. static const int ZAG[DCTSIZE2+16] = {
  521.   0,  1,  8, 16,  9,  2,  3, 10,
  522.  17, 24, 32, 25, 18, 11,  4,  5,
  523.  12, 19, 26, 33, 40, 48, 41, 34,
  524.  27, 20, 13,  6,  7, 14, 21, 28,
  525.  35, 42, 49, 56, 57, 50, 43, 36,
  526.  29, 22, 15, 23, 30, 37, 44, 51,
  527.  58, 59, 52, 45, 38, 31, 39, 46,
  528.  53, 60, 61, 54, 47, 55, 62, 63,
  529.   0,  0,  0,  0,  0,  0,  0,  0, /* extra entries in case k>63 below */
  530.   0,  0,  0,  0,  0,  0,  0,  0
  531. };
  532.  
  533.  
  534. /*
  535.  * Decode and return one MCU's worth of Huffman-compressed coefficients.
  536.  * The coefficients are reordered from zigzag order into natural array order,
  537.  * but are not dequantized.
  538.  *
  539.  * The i'th block of the MCU is stored into the block pointed to by
  540.  * MCU_data[i].  WE ASSUME THIS AREA HAS BEEN ZEROED BY THE CALLER.
  541.  * (Wholesale zeroing is usually a little faster than retail...)
  542.  *
  543.  * Returns FALSE if data source requested suspension.  In that case no
  544.  * changes have been made to permanent state.  (Exception: some output
  545.  * coefficients may already have been assigned.  This is harmless for
  546.  * this module, but would not work for decoding progressive JPEG.)
  547.  */
  548.  
  549. METHODDEF boolean
  550. decode_mcu (j_decompress_ptr cinfo, JBLOCKROW *MCU_data)
  551. {
  552.   huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
  553.   register int s, k, r;
  554.   int blkn, ci;
  555.   JBLOCKROW block;
  556.   working_state state;
  557.   D_DERIVED_TBL * dctbl;
  558.   D_DERIVED_TBL * actbl;
  559.   jpeg_component_info * compptr;
  560.  
  561.   /* Process restart marker if needed; may have to suspend */
  562.   if (cinfo->restart_interval) {
  563.     if (entropy->restarts_to_go == 0)
  564.       if (! process_restart(cinfo))
  565.     return FALSE;
  566.   }
  567.  
  568.   /* Load up working state */
  569.   state.unread_marker = cinfo->unread_marker;
  570.   state.next_input_byte = cinfo->src->next_input_byte;
  571.   state.bytes_in_buffer = cinfo->src->bytes_in_buffer;
  572.   ASSIGN_STATE(state.cur, entropy->saved);
  573.   state.cinfo = cinfo;
  574.  
  575.   /* Outer loop handles each block in the MCU */
  576.  
  577.   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
  578.     block = MCU_data[blkn];
  579.     ci = cinfo->MCU_membership[blkn];
  580.     compptr = cinfo->cur_comp_info[ci];
  581.     dctbl = entropy->dc_derived_tbls[compptr->dc_tbl_no];
  582.     actbl = entropy->ac_derived_tbls[compptr->ac_tbl_no];
  583.  
  584.     /* Decode a single block's worth of coefficients */
  585.  
  586.     /* Section F.2.2.1: decode the DC coefficient difference */
  587.     huff_DECODE(s, state, dctbl, label1);
  588.     if (s) {
  589.       check_bit_buffer(state, s, return FALSE);
  590.       r = get_bits(state, s);
  591.       s = huff_EXTEND(r, s);
  592.     }
  593.  
  594.     /* Shortcut if component's values are not interesting */
  595.     if (! compptr->component_needed)
  596.       goto skip_ACs;
  597.  
  598.     /* Convert DC difference to actual value, update last_dc_val */
  599.     s += state.cur.last_dc_val[ci];
  600.     state.cur.last_dc_val[ci] = s;
  601.     /* Output the DC coefficient (assumes ZAG[0] = 0) */
  602.     (*block)[0] = (JCOEF) s;
  603.  
  604.     /* Do we need to decode the AC coefficients for this component? */
  605.     if (compptr->DCT_scaled_size > 1) {
  606.  
  607.       /* Section F.2.2.2: decode the AC coefficients */
  608.       /* Since zeroes are skipped, output area must be cleared beforehand */
  609.       for (k = 1; k < DCTSIZE2; k++) {
  610.     huff_DECODE(s, state, actbl, label2);
  611.       
  612.     r = s >> 4;
  613.     s &= 15;
  614.       
  615.     if (s) {
  616.       k += r;
  617.       check_bit_buffer(state, s, return FALSE);
  618.       r = get_bits(state, s);
  619.       s = huff_EXTEND(r, s);
  620.       /* Output coefficient in natural (dezigzagged) order */
  621.       (*block)[ZAG[k]] = (JCOEF) s;
  622.     } else {
  623.       if (r != 15)
  624.         break;
  625.       k += 15;
  626.     }
  627.       }
  628.  
  629.     } else {
  630. skip_ACs:
  631.  
  632.       /* Section F.2.2.2: decode the AC coefficients */
  633.       /* In this path we just discard the values */
  634.       for (k = 1; k < DCTSIZE2; k++) {
  635.     huff_DECODE(s, state, actbl, label3);
  636.       
  637.     r = s >> 4;
  638.     s &= 15;
  639.       
  640.     if (s) {
  641.       k += r;
  642.       check_bit_buffer(state, s, return FALSE);
  643.       drop_bits(state, s);
  644.     } else {
  645.       if (r != 15)
  646.         break;
  647.       k += 15;
  648.     }
  649.       }
  650.  
  651.     }
  652.   }
  653.  
  654.   /* Completed MCU, so update state */
  655.   cinfo->unread_marker = state.unread_marker;
  656.   cinfo->src->next_input_byte = state.next_input_byte;
  657.   cinfo->src->bytes_in_buffer = state.bytes_in_buffer;
  658.   ASSIGN_STATE(entropy->saved, state.cur);
  659.  
  660.   /* Account for restart interval (no-op if not using restarts) */
  661.   entropy->restarts_to_go--;
  662.  
  663.   return TRUE;
  664. }
  665.  
  666.  
  667. /*
  668.  * Module initialization routine for Huffman entropy decoding.
  669.  */
  670.  
  671. GLOBAL void
  672. jinit_huff_decoder (j_decompress_ptr cinfo)
  673. {
  674.   huff_entropy_ptr entropy;
  675.   int i;
  676.  
  677.   entropy = (huff_entropy_ptr)
  678.     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
  679.                 SIZEOF(huff_entropy_decoder));
  680.   cinfo->entropy = (struct jpeg_entropy_decoder *) entropy;
  681.   entropy->pub.start_pass = start_pass_huff_decoder;
  682.   entropy->pub.decode_mcu = decode_mcu;
  683.  
  684.   /* Mark tables unallocated */
  685.   for (i = 0; i < NUM_HUFF_TBLS; i++) {
  686.     entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
  687.   }
  688. }
  689.